/**
 * @file   priority_queue.h
 * @author Linfufu
 * @date   Tue Dec 21 21:47:10 2021
 * 
 * @brief  priority_queue.h
 * 
 * 
 */

#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include <bits/stdc++.h>

template <typename Unique, typename Comparable>
struct DataBase
{
  Unique Key;//具有唯一性
  Comparable date;//具有可比性和可加减，但不具有唯一性
};

template <typename Unique, typename Comparable>
class priority_queue
{
  
 public:
  void insert(DateBase< Unique, Comparable > & _x)
  void deleteMin();
  void deleteMin( Comparable & minItem );
  void buildHeap( const std::vector< DataBase <Unique, Comparable> > & _input );
  void remove(Unique K);
  void modifyData( Unique k, Comparable d );
  bool isEmpty() const;
  void printArray();
  int sizeofqueue();

 private:
  int currentsize;//Number of elements in heap
  std::vector< DataBase<Unique, Comparable> > array;//The heap array
  void percolateDown( int hole );
  void percolateup( int hole );
};

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::insert( const DataBase<Unique, Comparable> &_x )//insert item x, allowing duplicates
  {
    if( currentsize == array.size() - 1 )
      array.resize( array.size() * 2 );
    int hole = ++currentsize;
    for( ; hole > 1 && x<array[ hole/2 ]; hole /=2 )
      array[hole] = array[hole/2];
    array[hole] = x;
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>:: deleteMin()//Remove the minimum item. Throws UnderflowException if empty.
  {
    if( isEmpty() )
      throw UnderflowException();

    array[1] = array [currentsize--];
    percolateDown(1);
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::deleteMin( Comparable  & minItem )//Remove the mininum item and place it in minItem. Throws UnderflowException if empty.
  {
    if( isEmpty() )
      throw UnderflowException();
    minItem = array[1];
    array[1] = array[currentsize--];
    percolateDown[1];
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::percolationDown( int hole )//Internal method to percolate down in the heap. hole is the index at which the percolate begins.
  {
    int child;
    DataBase<Unique, Comparable>  tmp = array[hole];

    for( ; hole * 2 <= currentsize; hole = child )
      {
	child = hole *2;
	if( child != currentsize && array[child + 1].data < array[ child ].data )
	  child++;
	if( array[child].data < tmp.data)
	  array[hole] = std::move(array[child]);
	else
	  break;
      }
    array[hole] = std::move(tmp);
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::perlocateup( int hole )
  {
    int father;
    DataBase<Unique, Comparable> tmp = array[hole];
    for( ; hole > 1; hole/=2)
      {
	father = hole/2;
	if(array[father].data > tmp.data)
	  array[hole] = std::move(array[father]);
	else
	  break;
      }
    array[hole] = std::move(tmp);
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>:: buildHeap( const std::vector<DataBase<Unique, Comparable>> & _input )
  {
    for( auto i: _input)
      {
	insert(i);
      }
  }

template <typename Unique, typename Comparable>
bool priority_queue<Unique, Comparable>:: isEmpty() const
  {
    return( currentsize == 0);
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::printArray()
  {
    for( int i=1; i<array.size(); i++)
      cout<<" "<<array[i].date;
    cout<<endl;
  }

template <typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>::modifyData( Unique k, Comparable d)
  {
    if( d== 0)
      return;
    else if(d<0)
      {
	for( int i=1; i<=currentsize; i++ )
	  {
	    if(array[i].Key == k)
	      {
		array[i].data += d;
		perlocateup(i);
		return;
	      }
	  }
      }
    else if( d>0)
      {
	for( int i = 1; i<=currentsize; i++ )
	  {
	    if(array[i].Key == k)
	      {
		array[i].data += d;
		perlocateDown(i);
		return;
	      }
	  }
      }
  }

template<typename Unique, typename Comparable>
void priority_queue<Unique, Comparable>:: remove( Unique k )
  {
    int position;

    for( position = 1; position <= currentsize; position++)
      {
	if(array[position].Key == k)
	  {
	    break;
	  }
      }
    if(position > currentsize)
      return;
    while(array[1].Key != k)
      {
	modifData(k, -1000);
      }
    deleteMin();
  }

template <typename Unique, typename Comparable>
int priority_queue<Unique, Comparable>::sizeofqueue()
{
  return currentsize;
}

#endif

